package Sq_Stack;
// 顺序栈
public class SqStack<T> {
    final int init_capacity=10;
    private T[] data;
    // top 永远指向栈顶，栈的指针
    private int top;
    private int capacity;

    public SqStack(){
        capacity = init_capacity;
        data = (T[]) new Object[capacity];
        top=-1;
    }

    // 更新栈的容量(更新容量总是使用新数组替换旧数组)
    public void update_capacity(int new_capacity){
        T[] new_data = (T[]) new Object[new_capacity];
        for(int i=0;i<capacity;i++){
            new_data[i] = data[i];
        }
        capacity = new_capacity;
        data = new_data;
    }

    // 判断栈是否为空(只需要判断指针是否指向栈底)
    public boolean empty(){
        return top==-1;
    }

    // 元素进栈
    public void push(T t){
        if(capacity == top+1){
            // 如果满了，容量变两倍
            update_capacity(2*(top+1));
        }
        // 先指向空位置
        top++;
        // 进栈
        data[top] = t;
    }

    // 元素出栈
    public T pop(){
        if(empty()){
            throw new IllegalArgumentException("栈空");
        }
        T t = data[top];
        // 改变指针指向
        top--;
        if(capacity>init_capacity&&top+1==capacity/4){
            update_capacity(capacity/2);
        }
        return t;
    }

    // 取栈顶元素
    public T peek(){
        if(empty()){
            throw new IllegalArgumentException("栈空");
        }
        return data[top];
    }

    //获取栈元素
    public int len(){
        return top+1;
    }
}
